package olga.gorbatiuk.perdep.sorting.sort.impl;

import olga.gorbatiuk.perdep.sorting.sort.Sort;

/**
 * @author Olga Gorbatiuk
 */
public class MergeSort implements Sort {

    /**
     * @see olga.gorbatiuk.perdep.sorting.sort.Sort#sort(int[])
     */
    @Override
    public void sort(int[] array) {
        int lowerBound = 0;
        int upperBound = array.length;
        sort(array, lowerBound, upperBound);
    }

    private void sort(int[] array, int lowerBound, int upperBound) {
        if (lowerBound + 1 < upperBound) {
            int mid = (lowerBound + upperBound) / 2;
            sort(array, lowerBound, mid);
            sort(array, mid, upperBound);

            int size = upperBound - lowerBound;
            int[] b = new int[size];

            int i = lowerBound;
            int j = mid;
            for (int k = 0; k < size; k++) {
                if (j >= upperBound || i < mid && array[i] < array[j]) {
                    b[k] = array[i++];
                } else {
                    b[k] = array[j++];
                }
            }
            System.arraycopy(b, 0, array, lowerBound, size);
        }
    }
}
